class Solution(object):
    def maxSumMinProduct(self, nums):
        n = len(nums)
        left_ans = [0] * n
        right_ans = [0] * n
        pre = [0] * n
        pre[0] = nums[0]
        for i in range(1, n):
            pre[i] = pre[i - 1] + nums[i]
        st = []
        for index, num in enumerate(nums):
            while st and nums[st[-1]] >= num:
                st.pop()
            if st:
                left_ans[index] = st[-1] + 1
            else:
                left_ans[index] = 0
            st.append(index)
        st = []
        for i in range(n - 1, -1, -1):
            while st and nums[st[-1]] >= nums[i]:
                st.pop()
            if st:
                right_ans[i] = st[-1] - 1
            else:
                right_ans[i] = n - 1
            st.append(i)
        max_val = 0
        for i in range(n):
            if left_ans[i] == 0:
                val = nums[i] * pre[right_ans[i]]
            else:
                val = nums[i] * (pre[right_ans[i]] - pre[left_ans[i] - 1])
            max_val = max(max_val, val)
        return max_val

data = Solution()
nums = [1,2,3,2]
print(data.maxSumMinProduct(nums))